`:top

In `F33f`_`[computational complexity theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computational_complexity_theory]`_`f and `F33f`_`[computability theory`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computability_theory]`_`f, a `!counting problem`! is a type of `F33f`_`[computational problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computational_problem]`_`f. If `*R`* is a `F33f`_`[search problem`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Search_problem]`_`f then

c R ( x ) = | { y ∣ ∣ R ( x , y ) } | {\\displaystyle c_{R}(x)=\\vert \\{y\\mid R(x,y)\\}\\vert \\,}

is the corresponding counting function and

# # R = { ( x , y ) ∣ ∣ y ≤ ≤ c R ( x ) } {\\displaystyle \\#R=\\{(x,y)\\mid y\\leq c_{R}(x)\\}}

denotes the corresponding decision problem.

Note that `*cR`* is a search problem while #`*R`* is a decision problem, however `*cR`* can be `*`!C`!`* `F33f`_`[Cook-reduced`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Cook_reduction]`_`f to #`*R`* (for appropriate `*`!C`!`*) using a `F33f`_`[binary search`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Binary_search]`_`f (the reason #`*R`* is defined the way it is, rather than being the graph of `*cR`*, is to make this binary search possible).

>>Contents

• `F0af`_`[Counting complexity class`#counting-complexity-class]`_`f

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

• `F0af`_`[External links`#external-links]`_`f

-─

>>Counting complexity class

Just as NP has `F33f`_`[NP-complete`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NP-complete]`_`f problems via `F33f`_`[many-one reductions`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Many-one_reduction]`_`f, #P has #P-complete problems via `F33f`_`[parsimonious reductions`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Parsimonious_reduction]`_`f, problem transformations that preserve the number of solutions.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f]

>>See also

• `F33f`_`[GapP`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=GapP]`_`f

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citerefbarak2006`aBarak, Boaz (Spring 2006). "Complexity of counting" (PDF). `*Princeton University`*.

>>External links

• "counting problem". `*`F33f`_`[PlanetMath`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PlanetMath]`_`f`*.

• "counting complexity class". `*`F33f`_`[PlanetMath`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=PlanetMath]`_`f`*.

`c`F0af`_`[↑ Back to top`#top]`_`f`a